// https://www.lintcode.com/problem/word-break-ii/description

class Solution {
public:
    /*
     * @param s: A string
     * @param wordDict: A set of words.
     * @return: All possible sentences.
     */
     
// 记忆化搜索与DP之间的关系？
// – 记忆化搜索是DP的一种实现方式
// – DP有两种实现方式
// 1. 递推
// 2. 记忆化搜索


    // Time Limit Exceeded
    // Input
    // "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
    // ["a","aa","aaa","aaaa","aaaaa","aaaaaa","aaaaaaa","aaaaaaaa","aaaaaaaaa","aaaaaaaaaa"]
    // Expected
    // []
    vector<string> dfs(string s, unordered_set<string> wordDict, map<string, vector<string>> &memo) {
        vector<string> result;
        if (memo.find(s) != memo.end())
        {
            return memo[s];
        }
        for (int i = 0; i < s.length() + 1; i++)
        {
            string s1 = s.substr(0, i);
           
            if (s1 != "" && wordDict.find(s1) != wordDict.end())
            {
                // Input
                // "a"
                // [""]
                // Expected
                // []
                if (i == s.length())
                {
                    result.push_back(s1);
                    return result;
                }
                else
                {
                    vector<string> r = dfs(s.substr(i, s.length()), wordDict, memo);
                    for (string rr: r)
                    {
                        result.push_back(s1 + " " + rr);
                    }
                }
            }
        }
        memo[s] = result;
        return result;    
    }
   
    vector<string> wordBreak(string &s, unordered_set<string> &wordDict) {
        vector<string> result;
        map<string, vector<string>> memo;
        result = findBreak(s, wordDict, memo);
        return result;
    }
};